{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Image Smoother"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: imageSmoother"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图片平滑器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>图像平滑器</strong> 是大小为&nbsp;<code>3 x 3</code> 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。</p>\n",
    "\n",
    "<p>每个单元格的<strong>&nbsp; 平均灰度</strong> 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。</p>\n",
    "\n",
    "<p>如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/05/03/smoother-grid.jpg\" style=\"height: 493px; width: 493px;\" /></p>\n",
    "\n",
    "<p>给你一个表示图像灰度的 <code>m x n</code> 整数矩阵 <code>img</code> ，返回对图像的每个单元格平滑处理后的图像&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/05/03/smooth-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>img = [[1,1,1],[1,0,1],[1,1,1]]\n",
    "<strong>输出:</strong>[[0, 0, 0],[0, 0, 0], [0, 0, 0]]\n",
    "<strong>解释:</strong>\n",
    "对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0\n",
    "对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0\n",
    "对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/03/smooth2-grid.jpg\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> img = [[100,200,100],[200,50,200],[100,200,100]]\n",
    "<strong>输出:</strong> [[137,141,137],[141,138,141],[137,141,137]]\n",
    "<strong>解释:</strong>\n",
    "对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137\n",
    "对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141\n",
    "对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == img.length</code></li>\n",
    "\t<li><code>n == img[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>0 &lt;= img[i][j] &lt;= 255</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [image-smoother](https://leetcode.cn/problems/image-smoother/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [image-smoother](https://leetcode.cn/problems/image-smoother/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,0,1],[1,1,1]]', '[[100,200,100],[200,50,200],[100,200,100]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(img),len(img[0])\n",
    "        # 构造二维列表\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        # 循环二位列表中的每一项\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 找到每一项周边和自身的单元格(不超过边界)\n",
    "                ttl,cnt = 0,0\n",
    "                for x in range(max(i-1,0),min(i+1+1,m)):\n",
    "                    for y in range(max(j-1,0),min(j+1+1,n)):\n",
    "                        ttl += img[x][y]\n",
    "                        cnt += 1\n",
    "                res[i][j] = ttl//cnt\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "class Solution:\r\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\r\n",
    "        row, col = len(img), len(img[0])\r\n",
    "        res = [[0] * col for _ in range(row)]\r\n",
    "        for r in range(row):\r\n",
    "            for c in range(col):\r\n",
    "                count, cur_sum = 0, 0\r\n",
    "                for cur_r in range(max(0, r-1), min(row-1, r+1) + 1):\r\n",
    "                    for cur_c in range(max(0, c-1), min(col-1, c+1) + 1):\r\n",
    "                        count += 1\r\n",
    "                        cur_sum += img[cur_r][cur_c]\r\n",
    "                res[r][c] = cur_sum // count\r\n",
    "        return res\r\n",
    "\r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(img), len(img[0])\n",
    "        res = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                c = 0\n",
    "                num = 0\n",
    "                for p in [-1, 0, 1]:\n",
    "                    for q in [-1, 0, 1]:\n",
    "                        if 0 <= i + p < n and 0 <= j + q < m:\n",
    "                            c += img[i + p][j + q]\n",
    "                            num += 1\n",
    "                res[i].append(c // num)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tot, num = 0, 0\n",
    "                for x in range(max(i - 1, 0), min(i + 2, m)):\n",
    "                    for y in range(max(j - 1, 0), min(j + 2, n)):\n",
    "                        tot += img[x][y]\n",
    "                        num += 1\n",
    "                ans[i][j] = tot // num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        # product: from itertools import product\n",
    "        # [[-1, 0, 1]] 是一个包含一个子列表 [-1, 0, 1] 的列表。\n",
    "        # *[[-1, 0, 1]] 中的 * 解包了这个列表，将子列表 [-1, 0, 1] 的内容取出。\n",
    "        # *[[-1, 0, 1]] * 2 表示将解包后的子列表 [-1, 0, 1] 重复两次，得到 [-1, 0, 1] 和 [-1, 0, 1]，然后将它们放在一个新的列表中。\n",
    "        # 所以，*[[-1, 0, 1]] * 2 的结果是一个包含两个相同子列表 [-1, 0, 1] 的列表。\n",
    "        dirs = list(product(*[[-1,0,1]] * 2))\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            tot, cnt = 0, 0\n",
    "            for di in dirs:\n",
    "                # := 是 Python 3.8+ 版本引入的新特性，称为\"walrus operator\"（海象运算符）。这个运算符的作用是同时进行赋值和表达式求值，将表达式的结果赋给左侧的变量。\n",
    "                if 0 <= (nx := i + di[0]) < m and 0 <= (ny := j + di[1]) < n:\n",
    "                    tot += img[nx][ny]\n",
    "                    cnt += 1\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans\n",
    "\n",
    "        #前缀和 之后学 看这个题https://leetcode.cn/problems/range-sum-query-2d-immutable/solutions/629362/xia-ci-ru-he-zai-30-miao-nei-zuo-chu-lai-ptlo/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        if img == []:\n",
    "            return []\n",
    "        m,n = len(img),len(img[0])\n",
    "        res = [[] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cnt, all = 0,0\n",
    "                for i2 in range(i-1, i+2):\n",
    "                    for j2 in range(j-1, j+2):\n",
    "                        if i2 in range(0,m) and j2 in range(0,n):\n",
    "                            cnt += 1\n",
    "                            all += img[i2][j2]\n",
    "                if cnt == 0:\n",
    "                    return img[i][j]\n",
    "\n",
    "                res[i].append(math.floor(all/cnt))\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(img),len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a = ans[i][j]\n",
    "                l,r,u,d,s = 1,2,1,2,0\n",
    "                if i == 0:\n",
    "                    u = 0\n",
    "                if i == m - 1:\n",
    "                    d = 1\n",
    "                if j == 0:\n",
    "                    l = 0\n",
    "                if j == n - 1:\n",
    "                    r = 1\n",
    "                for i0 in range(i-u,i+d):\n",
    "                    for j0 in range(j-l,j+r):\n",
    "                        s += img[i0][j0]\n",
    "                ans[i][j] = s // ((l+r) * (u+d))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        def getAvgGray(M,i,j,rows,cols):\n",
    "            count = 0\n",
    "            total = 0\n",
    "            for dx in [-1,0,1]:\n",
    "                for dy in [-1,0,1]:\n",
    "                    ni, nj = i+dx, j+dy\n",
    "                    if 0<=ni<rows and 0<=nj<cols:\n",
    "                        total += M[ni][nj]\n",
    "                        count += 1\n",
    "            return total // count\n",
    "            \n",
    "        if not img: return []\n",
    "        rows, cols = len(img), len(img[0])\n",
    "        res = [[0]*cols for _ in range(rows)]\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                res[i][j] = getAvgGray(img, i, j, rows, cols)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: list[list[int]]) -> list[list[int]]:\n",
    "        outcome = []\n",
    "        for i in range(len(img)):\n",
    "            outcome.append([])\n",
    "        for i, s in enumerate(img):\n",
    "            for j in range(len(s)):\n",
    "                number, times = 0, 0\n",
    "                # 第一格\n",
    "                try:\n",
    "                    if j - 1 >= 0 and i - 1 >= 0:\n",
    "                        number += img[i - 1][j - 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第二格\n",
    "                try:\n",
    "                    if i - 1 >= 0:\n",
    "                        number += img[i - 1][j]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第三格\n",
    "                try:\n",
    "                    if i - 1 >= 0:\n",
    "                        number += img[i - 1][j + 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第四格\n",
    "                if j - 1 >= 0:\n",
    "                    number += s[j - 1]\n",
    "                    times += 1\n",
    "                # 第五格\n",
    "                number += s[j]\n",
    "                times += 1\n",
    "                # 第六格\n",
    "                try:\n",
    "                    number += s[j + 1]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第七格\n",
    "                try:\n",
    "                    if j - 1 >= 0:\n",
    "                        number += img[i + 1][j - 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第八格\n",
    "                try:\n",
    "                    number += img[i + 1][j]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第九格\n",
    "                try:\n",
    "                    number += img[i + 1][j + 1]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "\n",
    "                outcome[i].append(number // times)\n",
    "        return outcome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[None] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c = 0\n",
    "                s = 0\n",
    "                for x in range(max(i-1, 0), min(i+2, m)):\n",
    "                    for y in range(max(j-1, 0), min(j+2, n)):\n",
    "                        c += 1\n",
    "                        s += img[x][y]\n",
    "                ans[i][j] = int(s / c)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(img)\n",
    "        n=len(img[0])\n",
    "        res=[[0 for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            start_line=max(i-1,0)\n",
    "            end_line=min(i+2,m)\n",
    "            for j in range(n):\n",
    "                start_col=max(j-1,0)\n",
    "                end_col=min(j+2,n)\n",
    "                count=(end_line-start_line)*(end_col-start_col)\n",
    "                sum_around=0\n",
    "                for v in range(start_line,end_line):\n",
    "                    for w in range(start_col,end_col):\n",
    "                        sum_around+=img[v][w]\n",
    "                res[i][j]=sum_around//count\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: list[list[int]]) -> list[list[int]]:\n",
    "        outcome = []\n",
    "        for i in range(len(img)):\n",
    "            outcome.append([])\n",
    "        for i, s in enumerate(img):\n",
    "            for j in range(len(s)):\n",
    "                number, times = 0, 0\n",
    "                # 第一格\n",
    "                try:\n",
    "                    if j - 1 >= 0 and i - 1 >= 0:\n",
    "                        number += img[i - 1][j - 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第二格\n",
    "                try:\n",
    "                    if i - 1 >= 0:\n",
    "                        number += img[i - 1][j]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第三格\n",
    "                try:\n",
    "                    if i - 1 >= 0:\n",
    "                        number += img[i - 1][j + 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第四格\n",
    "                if j - 1 >= 0:\n",
    "                    number += s[j - 1]\n",
    "                    times += 1\n",
    "                # 第五格\n",
    "                number += s[j]\n",
    "                times += 1\n",
    "                # 第六格\n",
    "                try:\n",
    "                    number += s[j + 1]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第七格\n",
    "                try:\n",
    "                    if j - 1 >= 0:\n",
    "                        number += img[i + 1][j - 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第八格\n",
    "                try:\n",
    "                    number += img[i + 1][j]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第九格\n",
    "                try:\n",
    "                    number += img[i + 1][j + 1]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "\n",
    "                outcome[i].append(number // times)\n",
    "        return outcome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.times = 0\n",
    "\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        # python中多维数组的深拷贝不能够用copy\n",
    "        # b = a 浅拷贝\n",
    "        # b = a.copy() 浅拷贝，对一级目录，即a进行深拷贝，但是对a里面的对象型数据进行的还是浅拷贝\n",
    "        # b = copy.deepcopy() 深拷贝，对a之中的对象也进行深拷贝\n",
    "        # for i in img:\n",
    "        #     res.append(i.copy())\n",
    "        res = copy.deepcopy(img)\n",
    "        for i in range(len(img)):\n",
    "            for j in range(len(img[0])):\n",
    "                cum = 0\n",
    "                cum += self.calculateSum(img, i - 1, j - 1, j + 1)\n",
    "                cum += self.calculateSum(img, i, j - 1, j + 1)\n",
    "                cum += self.calculateSum(img, i + 1, j - 1, j + 1)\n",
    "                res[i][j] = math.floor(cum / self.times)\n",
    "                self.times = 0\n",
    "        return res\n",
    "\n",
    "    def calculateSum(self, img, row, start, end):\n",
    "        if row < 0 or row >= len(img):\n",
    "            return 0\n",
    "        cum = 0\n",
    "        while start <= end and start < len(img[0]):\n",
    "            if 0 <= start < len(img[0]):\n",
    "                cum += img[row][start]\n",
    "                self.times += 1\n",
    "            start += 1\n",
    "        return cum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        if img == []:\n",
    "            return []\n",
    "        m,n = len(img),len(img[0])\n",
    "        res = [[] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cnt, all = 0,0\n",
    "                for i2 in range(max(0,i-1), min(m,i+2)):\n",
    "                    for j2 in range(max(0,j-1), min(n,j+2)):\n",
    "                        \n",
    "                        cnt += 1\n",
    "                        all += img[i2][j2]\n",
    "                if cnt == 0:\n",
    "                    return img[i][j]\n",
    "\n",
    "                res[i].append(math.floor(all/cnt))\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        temp_list = []\n",
    "        new_list = []\n",
    "        direc_list = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]\n",
    "\n",
    "        for i in range(len(img)):\n",
    "            temp_list = []\n",
    "            for j in range(len(img[0])):\n",
    "                sum_num = img[i][j]\n",
    "                count = 1\n",
    "                for x, y in direc_list:\n",
    "                    new_x = i + x\n",
    "                    new_y = j + y\n",
    "                    if  0 <= new_x < len(img) and 0 <= new_y < len(img[0]):\n",
    "                        sum_num += img[new_x][new_y]\n",
    "                        count += 1\n",
    "\n",
    "                temp_list.append(sum_num // count)\n",
    "            new_list.append(copy.deepcopy(temp_list))\n",
    "\n",
    "        return new_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m, n = len(img), len(img[0])\n",
    "\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            for j in range(n):\n",
    "                r = sum([sum(i[max(0, j-1): min(j+2, n)]) for i in img[max(i-1, 0): min(m, i+2)]])\n",
    "                length_nums = (min(j+2, n)-max(0, j-1)) *  (min(m, i+2) - max(i-1, 0))\n",
    "                \n",
    "                tmp.append(r//length_nums)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(img),len(img[0])\n",
    "        ml = []\n",
    "        for i in range(m):\n",
    "            nl = []\n",
    "            for j in range(n):\n",
    "                centre = (i,j)\n",
    "                all_point = []\n",
    "                for s in range(-1,2):\n",
    "                    for t in range(-1,2):\n",
    "                        if 0 <= i-s < m and 0 <= j-t < n:\n",
    "        #                     all_point.append((i-s,j-t))\n",
    "                            x = img[i-s][j-t]\n",
    "                            all_point.append(x)\n",
    "                nl.append(sum(all_point)//len(all_point))\n",
    "            # print(nl)\n",
    "            ml.append(nl)\n",
    "        return ml"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        w, h = len(img[0]), len(img)\n",
    "        ans = [[1 for i in range(w)] for j in range(h)]\n",
    "        dirs = [-1, 0, 1]\n",
    "        for i in range(w):\n",
    "            for j in range(h):\n",
    "                t = 0\n",
    "                cnt = 0\n",
    "                for k in dirs:\n",
    "                    for l in dirs:\n",
    "                        if 0 <= i + k < w and 0 <= j + l < h:\n",
    "                            t += img[j+l][i+k] \n",
    "                            cnt += 1\n",
    "                ans[j][i] = t // cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tot, num = 0, 0\n",
    "                for x in range(max(i - 1, 0), min(i + 2, m)):\n",
    "                    for y in range(max(j - 1, 0), min(j + 2, n)):\n",
    "                        tot += img[x][y]\n",
    "                        num += 1\n",
    "                ans[i][j] = tot // num\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        n=len(img[0])\n",
    "        \n",
    "        M=[[0.5]+row+[0.5] for row in img]\n",
    "        M=[[0.5]*(n+2)]+M+[[0.5]*(n+2)]\n",
    "        for i in range(1,len(M)-1):\n",
    "            for j in range(1,len(M[0])-1):\n",
    "                total=[M[i-1][j-1],M[i][j-1],M[i+1][j-1],M[i-1][j],M[i][j],M[i+1][j],M[i-1][j+1],M[i][j+1],M[i+1][j+1]]\n",
    "                sums,k=0,0\n",
    "                for _ in total:\n",
    "                    if _ !=0.5:\n",
    "                        sums+=_\n",
    "                    else:\n",
    "                        k+=1\n",
    "                img[i-1][j-1]=int(sums/(9-k))\n",
    "        return img\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tot, num = 0, 0\n",
    "                for x in range(max(i - 1, 0), min(i + 2, m)):\n",
    "                    for y in range(max(j - 1, 0), min(j + 2, n)):\n",
    "                        tot += img[x][y]\n",
    "                        num += 1\n",
    "                ans[i][j] = tot // num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        nimg = [[0 for j in i] for i in img]\n",
    "        n, m = len(img), len(img[0])\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                nimg[x][y] += sum(img[i][j] for i in range(max(0, x - 1), min(n, x + 2)) for j in range(max(0, y - 1), min(m, y + 2))) // ((min(n, x + 2) - max(0, x - 1)) * (min(m, y + 2) - max(0, y - 1)))\n",
    "        return nimg\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        w, h = len(img[0]), len(img)\n",
    "        ans = [[1]*w for j in range(h)]\n",
    "        dirs = [-1, 0, 1]\n",
    "        for i in range(w):\n",
    "            for j in range(h):\n",
    "                t = 0\n",
    "                cnt = 0\n",
    "                for k in dirs:\n",
    "                    for l in dirs:\n",
    "                        if 0 <= i + k < w and 0 <= j + l < h:\n",
    "                            t += img[j+l][i+k] \n",
    "                            cnt += 1\n",
    "                ans[j][i] = t // cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                total, cnt = 0, 0\n",
    "                for x in range(max(i-1, 0), min(i+2, m)):\n",
    "                    for y in range(max(j-1, 0), min(j+2, n)):\n",
    "                        total += img[x][y]\n",
    "                        cnt += 1\n",
    "                ans[i][j] = total // cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img):\n",
    "        m, n = len(img), len(img[0])\n",
    "        result = [[0] * n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                total_sum = 0\n",
    "                count = 0\n",
    "                \n",
    "                for x in range(i - 1, i + 2):\n",
    "                    for y in range(j - 1, j + 2):\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            total_sum += img[x][y]\n",
    "                            count += 1\n",
    "                \n",
    "                result[i][j] = total_sum // count\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        smoothed = [[0 for i in j] for j in img]\n",
    "        m, n = len(smoothed), len(smoothed[0])\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                neighbour = [(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1),(x,y),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)]\n",
    "                neighbourhood = []\n",
    "                for antris in neighbour:\n",
    "                    if 0 <= antris[0] < m and 0 <= antris[1] < n:\n",
    "                        neighbourhood.append(img[antris[0]][antris[1]])\n",
    "                smoothed[x][y] = sum(neighbourhood) // len(neighbourhood)\n",
    "        return smoothed\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        # if not img:\n",
    "        #     return \n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tot, num = 0, 0\n",
    "                for x in range(max(i - 1, 0), min(i + 2, m)):\n",
    "                    for y in range(max(j - 1, 0), min(j + 2, n)):\n",
    "                        tot += img[x][y]\n",
    "                        num += 1\n",
    "                ans[i][j] = tot // num\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(img)\n",
    "        n = len(img[0])\n",
    "\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                count = 0\n",
    "                sum_ = 0\n",
    "                for t in range(max(i - 1, 0), min(i + 2, m)):\n",
    "                    for k in range(max(j - 1, 0), min(j + 2, n)):\n",
    "                        count += 1\n",
    "                        sum_ += img[t][k]\n",
    "\n",
    "                res[i][j] = sum_ // count\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        new_img = [[0 for y in range(len(img[0]))] for x in range(len(img))]\n",
    "        for r in range(len(img)):\n",
    "            for c in range(len(img[0])):\n",
    "                sum_r_start = max(r - 1, 0)\n",
    "                sum_r_end = min(r + 1, len(img) - 1)\n",
    "                sum_c_start = max(c - 1, 0)\n",
    "                sum_c_end = min(c + 1, len(img[0]) - 1)\n",
    "                sumrc = 0\n",
    "                countrc = 0\n",
    "                for sumr in range(sum_r_start, sum_r_end + 1):\n",
    "                    for sumc in range(sum_c_start, sum_c_end + 1):\n",
    "                        sumrc = sumrc + img[sumr][sumc]\n",
    "                        countrc = countrc + 1\n",
    "                new_img[r][c] = int(sumrc / countrc)\n",
    "        return new_img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        rows, cols = len(img), len(img[0])\n",
    "        ans = deepcopy(img)\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                neighbors = [\n",
    "                    img[dx][dy]\n",
    "                    for dx in (r-1, r, r+1)\n",
    "                    for dy in (c-1, c, c+1)\n",
    "                    if 0 <= dx < rows and 0 <= dy < cols\n",
    "                ]\n",
    "                ans[r][c] = sum(neighbors) // len(neighbors)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        outcome = []\n",
    "        for i in range(len(img)):\n",
    "            outcome.append([])\n",
    "        for i, s in enumerate(img):\n",
    "            for j in range(len(s)):\n",
    "                number, times = 0, 0\n",
    "                # 第一格\n",
    "                try:\n",
    "                    if j - 1 >= 0 and i - 1 >= 0:\n",
    "                        number += img[i - 1][j - 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第二格\n",
    "                try:\n",
    "                    if i - 1 >= 0:\n",
    "                        number += img[i - 1][j]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第三格\n",
    "                try:\n",
    "                    if i - 1 >= 0:\n",
    "                        number += img[i - 1][j + 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第四格\n",
    "                if j - 1 >= 0:\n",
    "                    number += s[j - 1]\n",
    "                    times += 1\n",
    "                # 第五格\n",
    "                number += s[j]\n",
    "                times += 1\n",
    "                # 第六格\n",
    "                try:\n",
    "                    number += s[j + 1]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第七格\n",
    "                try:\n",
    "                    if j - 1 >= 0:\n",
    "                        number += img[i + 1][j - 1]\n",
    "                        times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第八格\n",
    "                try:\n",
    "                    number += img[i + 1][j]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "                # 第九格\n",
    "                try:\n",
    "                    number += img[i + 1][j + 1]\n",
    "                    times += 1\n",
    "                except IndexError:\n",
    "                    number = number\n",
    "\n",
    "                outcome[i].append(number // times)\n",
    "        return outcome\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = list(product(*[[-1,0,1]] * 2))\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            tot, cnt = 0, 0\n",
    "            for di in dirs:\n",
    "                if 0 <= (nx := i + di[0]) < m and 0 <= (ny := j + di[1]) < n:\n",
    "                    tot += img[nx][ny]\n",
    "                    cnt += 1\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        res=[[0]*len(img[0]) for j in range (len(img))]\n",
    "        for j in range(len(img[0])):#列数\n",
    "            for i in range(len(img)):#行数\n",
    "                sum=0#相加的和\n",
    "                num=0#相加的数字和\n",
    "        #对于第i行第j列,向左为max(i-1,0)不可能越界0,向右min(i+1,len(img[0])-1)不会越过最大界限,向下max(j-1,0),向上min(j+1,len(img)-1)\n",
    "                #这几行求和\n",
    "                for x in range(max(i-1,0),min(i+1,len(img)-1)+1):\n",
    "                   #这几列求和\n",
    "                    for y in range(max(j-1,0),min(j+1,len(img[0])-1)+1):\n",
    "                       sum+=img[x][y]\n",
    "                       num+=1\n",
    "                res[i][j]=int(sum//num)  \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        # 注:\n",
    "        #  本程序在各个计算过程中不进行逻辑判断，因此节省了一定的时间\n",
    "        #  但是当矩形等于 2 * 2 时，会进行很多多余的计算与判断（但是求解这么小的矩形本身就很快）\n",
    "\n",
    "        # 获取矩形的长和宽，并创建矩形（用来存放计算结果）\n",
    "        ans = []\n",
    "        h = len(img)\n",
    "        while h > 0:\n",
    "            ans.append([0] * len(img[0]))\n",
    "            h -= 1\n",
    "        w, h = len(img[0]), len(img) # 宽、高\n",
    "\n",
    "        # 矩形的尺寸为 1 * N 或 N * 1 时，需要单独处理\n",
    "        if w == 1 and h == 1: # 1 * 1\n",
    "            return img\n",
    "        elif h == 1 and w != 1: # 1 * N\n",
    "            ans[0][0] = (img[0][0] + img[0][1]) // 2\n",
    "            ans[0][w - 1] = (img[0][w - 2] + img[0][w - 1]) // 2\n",
    "            print(ans)\n",
    "            for i in range(1, w - 1):\n",
    "                ans[0][i] = (img[0][i - 1] + img[0][i] + img[0][i + 1]) // 3\n",
    "                i += 1\n",
    "            return ans\n",
    "        elif h != 1 and w == 1: # N * 1\n",
    "            ans[0][0] = (img[0][0] + img[1][0]) // 2\n",
    "            ans[h - 1][0] = (img[h - 2][0] + img[h - 1][0]) // 2\n",
    "            for i in range(1, h - 1):\n",
    "                ans[i][0] = (img[i - 1][0] + img[i][0] + img[i + 1][0]) // 3\n",
    "                i += 1\n",
    "            return ans\n",
    "        \n",
    "        # 确定矩形四个角的值\n",
    "        ans[0][0] = (img[0][0] + img[0][1] + img[1][0] + img[1][1]) // 4\n",
    "        ans[0][w - 1] = (img[0][w - 1] + img [0][w - 2] + img[1][w - 1] + img[1][w - 2]) // 4\n",
    "        ans[h - 1][0] = (img[h - 1][0] + img [h - 1][1] + img[h - 2][0] + img[h - 2][1]) // 4\n",
    "        ans[h - 1][w - 1] = (img[h - 1][w - 1] + img [h - 2][w - 1] + img[h - 1][w - 2] + img[h - 2][w - 2]) // 4\n",
    "        \n",
    "        # 确定矩形各边上单元格的值\n",
    "        r, c = 0, 1 # 行数、列数\n",
    "        while c < w - 1: # 第一行（去掉2个角）\n",
    "            ans[r][c] = (img[r][c-1] + img[r][c] + img[r][c+1] + img[r+1][c-1] + img[r+1][c] + img[r+1][c+1]) // 6\n",
    "            c += 1\n",
    "        r, c = h - 1, 1\n",
    "        while c < w - 1: # 最后一行（去掉2个角）\n",
    "            ans[r][c] = (img[r][c-1] + img[r][c] + img[r][c+1] + img[r-1][c-1] + img[r-1][c] + img[r-1][c+1]) // 6\n",
    "            c += 1\n",
    "        r, c = 1, 0\n",
    "        while r < h - 1: # 第一列（去掉2个角）\n",
    "            ans[r][c] = (img[r-1][c] + img[r][c] + img[r+1][c] + img[r-1][c+1] +img[r][c+1] + img[r+1][c+1]) // 6\n",
    "            r += 1\n",
    "        r, c = 1, w - 1\n",
    "        while r < h - 1: # 最后一列（去掉2个角）\n",
    "            ans[r][c] = (img[r-1][c] + img[r][c] + img[r+1][c] + img[r-1][c-1] +img[r][c-1] + img[r+1][c-1]) // 6\n",
    "            r += 1\n",
    "        \n",
    "        # 确定矩形内部各单元格的值\n",
    "        r = 1\n",
    "        while r < h - 1:\n",
    "            c = 1\n",
    "            while c < w - 1:\n",
    "                ans[r][c] = (img[r-1][c-1] + img[r-1][c] + img[r-1][c+1] + img[r][c-1] + img[r][c] + img[r][c+1] + img[r+1][c-1] + img[r+1][c] + img[r+1][c+1]) // 9\n",
    "                c += 1\n",
    "            r += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        x, y = 0, 0\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for x in range(m):\n",
    "            row = list()\n",
    "            for y in range(n):\n",
    "                total, count = 0, 0\n",
    "                for i in range(x-1, x+2):\n",
    "                    for j in range(y-1, y+2):\n",
    "                        if i >= 0 and j >= 0 and i < m and j < n:\n",
    "                            count += 1\n",
    "                            total += img[i][j]\n",
    "                ans[x][y] = total // count\n",
    "        return ans\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = list(product(*[[-1,0,1]] * 2))\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            tot, cnt = 0, 0\n",
    "            for di in dirs:\n",
    "                if 0 <= (nx := i + di[0]) < m and 0 <= (ny := j + di[1]) < n:\n",
    "                    tot += img[nx][ny]\n",
    "                    cnt += 1\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        smoothed = [[0 for i in j] for j in img]\n",
    "        m, n = len(smoothed), len(smoothed[0])\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                neighbour = [(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1),(x,y),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)]\n",
    "                neighbourhood = []\n",
    "                for antris in neighbour:\n",
    "                    if 0 <= antris[0] < m and 0 <= antris[1] < n:\n",
    "                        neighbourhood.append(img[antris[0]][antris[1]])\n",
    "                smoothed[x][y] = sum(neighbourhood) // len(neighbourhood)\n",
    "        return smoothed\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(img)\n",
    "        n=len(img[0])\n",
    "        res=[[0 for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            start_line=max(i-1,0)\n",
    "            end_line=min(i+2,m)\n",
    "            for j in range(n):\n",
    "                start_col=max(j-1,0)\n",
    "                end_col=min(j+2,n)\n",
    "                count=(end_line-start_line)*(end_col-start_col)\n",
    "                sum_around=0\n",
    "                for v in range(start_line,end_line):\n",
    "                    for w in range(start_col,end_col):\n",
    "                        sum_around+=img[v][w]\n",
    "                print(sum_around)\n",
    "                res[i][j]=sum_around//count\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        dx, dy = [-1,-1,-1,0,0,1,1,1], [1,0,-1,1,-1,1,0,-1]\n",
    "        m, n = len(img), len(img[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s = img[i][j]\n",
    "                cnt = 1\n",
    "                for k in range(8):\n",
    "                    a, b = i + dx[k], j + dy[k]\n",
    "                    if 0 <= a < m and 0 <= b < n:\n",
    "                        cnt += 1\n",
    "                        s += img[a][b]\n",
    "                res[i][j] = s // cnt if s * cnt != 0 else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(img)\n",
    "        n=len(img[0])\n",
    "        res=[[0 for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            start_line=max(i-1,0)\n",
    "            end_line=min(i+1,m-1)\n",
    "            for j in range(n):\n",
    "                start_col=max(j-1,0)\n",
    "                end_col=min(j+1,n-1)\n",
    "                count=(end_line-start_line+1)*(end_col-start_col+1)\n",
    "                sum_around=0\n",
    "                for v in range(start_line,end_line+1):\n",
    "                    for w in range(start_col,end_col+1):\n",
    "                        sum_around+=img[v][w]\n",
    "                print(sum_around)\n",
    "                res[i][j]=int(sum_around/count)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        row=len(img) #行数\n",
    "        col=len(img[0]) #列数\n",
    "        res = [[0]*col for i in range(row)]\n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                sum=img[i][j] #中\n",
    "                count=1\n",
    "                if i-1>=0 and j-1>=0: #左上\n",
    "                    sum+=img[i-1][j-1]\n",
    "                    count+=1\n",
    "                if i>=0 and j-1>=0: #左中\n",
    "                    sum+=img[i][j-1]\n",
    "                    count+=1\n",
    "                if i+1<row and j-1>=0: #左下\n",
    "                    sum+=img[i+1][j-1]\n",
    "                    count+=1\n",
    "                if i-1>=0 and j>=0: #中上\n",
    "                    sum+=img[i-1][j]\n",
    "                    count+=1\n",
    "                if i+1<row and j>=0: #中下\n",
    "                    sum+=img[i+1][j]\n",
    "                    count+=1\n",
    "                if i-1>=0 and j+1<col: #右上\n",
    "                    sum+=img[i-1][j+1]\n",
    "                    count+=1\n",
    "                if i>=0 and j+1<col: #右中\n",
    "                    sum+=img[i][j+1]\n",
    "                    count+=1\n",
    "                if i+1<row and j+1<col: #右下\n",
    "                    sum+=img[i+1][j+1]\n",
    "                    count+=1\n",
    "                res[i][j] = sum//count\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        a = [[0]*len(img[0]) for _ in range(len(img))]\n",
    "        for i in range(len(img)):\n",
    "            for j in range(len(img[0])):\n",
    "                sums = []\n",
    "                sums.append(img[i][j])\n",
    "                if i-1 >= 0:\n",
    "                    sums.append(img[i-1][j])\n",
    "                    if j-1 >= 0:\n",
    "                        sums.append(img[i-1][j-1])\n",
    "                    if j+1 <= len(img[0])-1:\n",
    "                        sums.append(img[i-1][j+1])\n",
    "                if j-1 >= 0:\n",
    "                    sums.append(img[i][j-1])\n",
    "                if j+1 <= len(img[0])-1:\n",
    "                    sums.append(img[i][j+1])\n",
    "                if i+1 <= len(img)-1:\n",
    "                    sums.append(img[i+1][j])\n",
    "                    if j-1 >= 0:\n",
    "                        sums.append(img[i+1][j-1])\n",
    "                    if j+1 <= len(img[0])-1:\n",
    "                        sums.append(img[i+1][j+1])\n",
    "                a[i][j] = sum(sums) // (len(sums))\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        # 注:\n",
    "        #  本程序在各个计算过程中不进行逻辑判断，因此节省了一定的时间\n",
    "        #  但是当矩形等于 2 * 2 时，会进行很多多余的计算与判断（但是求解这么小的矩形本身就很快）\n",
    "\n",
    "        # 获取矩形的长和宽，并创建矩形（用来存放计算结果）\n",
    "        ans = []\n",
    "        h = len(img)\n",
    "        while h > 0:\n",
    "            ans.append([0] * len(img[0]))\n",
    "            h -= 1\n",
    "        w, h = len(img[0]), len(img) # 宽、高\n",
    "\n",
    "        # 矩形的尺寸为 1 * N 或 N * 1 时，需要单独处理\n",
    "        if w == 1 and h == 1: # 1 * 1\n",
    "            return img\n",
    "        elif h == 1 and w != 1: # 1 * N\n",
    "            ans[0][0] = (img[0][0] + img[0][1]) // 2\n",
    "            ans[0][w - 1] = (img[0][w - 2] + img[0][w - 1]) // 2\n",
    "            print(ans)\n",
    "            for i in range(1, w - 1):\n",
    "                ans[0][i] = (img[0][i - 1] + img[0][i] + img[0][i + 1]) // 3\n",
    "                i += 1\n",
    "            return ans\n",
    "        elif h != 1 and w == 1: # N * 1\n",
    "            ans[0][0] = (img[0][0] + img[1][0]) // 2\n",
    "            ans[h - 1][0] = (img[h - 2][0] + img[h - 1][0]) // 2\n",
    "            for i in range(1, h - 1):\n",
    "                ans[i][0] = (img[i - 1][0] + img[i][0] + img[i + 1][0]) // 3\n",
    "                i += 1\n",
    "            return ans\n",
    "        \n",
    "        # 确定矩形四个角的值\n",
    "        ans[0][0] = (img[0][0] + img[0][1] + img[1][0] + img[1][1]) // 4\n",
    "        ans[0][w - 1] = (img[0][w - 1] + img [0][w - 2] + img[1][w - 1] + img[1][w - 2]) // 4\n",
    "        ans[h - 1][0] = (img[h - 1][0] + img [h - 1][1] + img[h - 2][0] + img[h - 2][1]) // 4\n",
    "        ans[h - 1][w - 1] = (img[h - 1][w - 1] + img [h - 2][w - 1] + img[h - 1][w - 2] + img[h - 2][w - 2]) // 4\n",
    "        \n",
    "        # 确定矩形各边上单元格的值\n",
    "        r, c = 0, 1 # 行数、列数\n",
    "        while c < w - 1: # 第一行（去掉2个角）\n",
    "            ans[r][c] = (img[r][c-1] + img[r][c] + img[r][c+1] + img[r+1][c-1] + img[r+1][c] + img[r+1][c+1]) // 6\n",
    "            c += 1\n",
    "        r, c = h - 1, 1\n",
    "        while c < w - 1: # 最后一行（去掉2个角）\n",
    "            ans[r][c] = (img[r][c-1] + img[r][c] + img[r][c+1] + img[r-1][c-1] + img[r-1][c] + img[r-1][c+1]) // 6\n",
    "            c += 1\n",
    "        r, c = 1, 0\n",
    "        while r < h - 1: # 第一列（去掉2个角）\n",
    "            ans[r][c] = (img[r-1][c] + img[r][c] + img[r+1][c] + img[r-1][c+1] +img[r][c+1] + img[r+1][c+1]) // 6\n",
    "            r += 1\n",
    "        r, c = 1, w - 1\n",
    "        while r < h - 1: # 最后一列（去掉2个角）\n",
    "            ans[r][c] = (img[r-1][c] + img[r][c] + img[r+1][c] + img[r-1][c-1] +img[r][c-1] + img[r+1][c-1]) // 6\n",
    "            r += 1\n",
    "        \n",
    "        # 确定矩形内部各单元格的值\n",
    "        r = 1\n",
    "        while r < h - 1:\n",
    "            c = 1\n",
    "            while c < w - 1:\n",
    "                ans[r][c] = (img[r-1][c-1] + img[r-1][c] + img[r-1][c+1] + img[r][c-1] + img[r][c] + img[r][c+1] + img[r+1][c-1] + img[r+1][c] + img[r+1][c+1]) // 9\n",
    "                c += 1\n",
    "            r += 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sum_ = 0\n",
    "                num = 0 \n",
    "                for i1 in range(max(0, i-1), min(i+2, m)):\n",
    "                    for j1 in range(max(0, j-1), min(j+2, n)):\n",
    "                        sum_+=img[i1][j1]\n",
    "                        num+=1\n",
    "                ans[i][j] = sum_ // num\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(img[0])    # 行的长度，即列数\n",
    "        m = len(img)    # 列的长度，即行数\n",
    "        res = [[0] * n for i in range(m)]\n",
    "    #对于第j行第i列,向左为max(j-1,0)不可能越界0,向右min(j+1,len(img)-1)不会越过最大界限,向下max(i-1,0),向上min(i+1,len(img[0])-1)\n",
    "        for i in range(n):  # i表示在第几列\n",
    "            for j in range(m):  # j表示在第几行\n",
    "                sum1 = 0\n",
    "                num1 = 0\n",
    "                for x in range(max(j-1, 0), min(j+1, m-1) + 1): # 这几行求和\n",
    "                    for y in range(max(i-1, 0), min(i+1, n-1) + 1): # 这几列求和\n",
    "                        sum1 += img[x][y]\n",
    "                        num1 += 1\n",
    "                res[j][i] = int(sum1/num1)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tot, num = 0, 0\n",
    "                for x in range(max(i-1, 0), min(i+2, m)):\n",
    "                    for y in range(max(j-1, 0), min(j+2, n)):\n",
    "                        tot += img[x][y]\n",
    "                        num += 1\n",
    "                    \n",
    "                ans[i][j] = tot // num\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = list(product(*[[-1,0,1]] * 2))\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            tot, cnt = 0, 0\n",
    "            for di in dirs:\n",
    "                if 0 <= (nx := i + di[0]) < m and 0 <= (ny := j + di[1]) < n:\n",
    "                    tot += img[nx][ny]\n",
    "                    cnt += 1\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(img)\n",
    "        n = len(img[0])\n",
    "        ans = [[0]* n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                total, count = 0, 0\n",
    "                for x in range(max(0, i-1), min(i+2,m)):\n",
    "                    for y in range(max(0,j-1), min(j+2,n)):\n",
    "                        total += img[x][y]\n",
    "                        count += 1\n",
    "                ans[i][j] = total // count\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        ret = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mi, mj = i - 1, i + 1\n",
    "                ni, nj = j - 1, j + 1\n",
    "\n",
    "                if mi < 0:\n",
    "                    mi = 0\n",
    "                if mj >= m:\n",
    "                    mj = m - 1\n",
    "\n",
    "                if ni < 0:\n",
    "                    ni = 0\n",
    "                if nj >= n:\n",
    "                    nj = n - 1\n",
    "\n",
    "                count = 0\n",
    "                sums = 0\n",
    "                for x in range(mi,mj + 1):\n",
    "                    for y in range(ni, nj + 1):\n",
    "                        count += 1\n",
    "                        sums += img[x][y]\n",
    "                \n",
    "                ret[i][j] = sums // count\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        pre_sum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i+1][j+1] = pre_sum[i+1][j] +pre_sum[i][j+1] \\\n",
    "                                    - pre_sum[i][j] + img[i][j]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                row_l, row_r = max(0, i-1), min(m-1, i+1)\n",
    "                col_l, col_r = max(0, j-1), min(n-1, j+1)\n",
    "                img[i][j] = (pre_sum[row_r+1][col_r+1]-pre_sum[row_r+1][col_l]\n",
    "                            -pre_sum[row_l][col_r+1]+pre_sum[row_l][col_l]) \\\n",
    "                            // ((row_r-row_l+1)*(col_r-col_l+1))\n",
    "        return img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(img)\n",
    "        n = len(img[0])\n",
    "        new = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def helper(x, y):\n",
    "            total = img[x][y]\n",
    "            nu = 1\n",
    "            if x - 1 >= 0 and y - 1 >= 0:  # 1\n",
    "                total += img[x - 1][y - 1]\n",
    "                nu += 1\n",
    "\n",
    "            if x - 1 >= 0:  # 2\n",
    "                total += img[x - 1][y]\n",
    "                nu += 1\n",
    "\n",
    "            if x - 1 >= 0 and y + 1 < n:  # 3\n",
    "                total += img[x - 1][y + 1]\n",
    "                nu += 1\n",
    "\n",
    "            if y + 1 < n:  # 4\n",
    "                total += img[x][y + 1]\n",
    "                nu += 1\n",
    "\n",
    "            if x + 1 < m and y + 1 < n:  # 5\n",
    "                total += img[x + 1][y + 1]\n",
    "                nu += 1\n",
    "\n",
    "            if x + 1 < m:  # 6\n",
    "                total += img[x + 1][y]\n",
    "                nu += 1\n",
    "\n",
    "            if x + 1 < m and y - 1 >= 0:  # 7\n",
    "                total += img[x + 1][y - 1]\n",
    "                nu += 1\n",
    "\n",
    "            if y - 1 >= 0:  # 8\n",
    "                total += img[x][y - 1]\n",
    "                nu += 1\n",
    "\n",
    "            # print(total, nu)\n",
    "            return int(total / nu)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                new[i][j] = helper(i, j)\n",
    "\n",
    "        return new\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: list[list[int]]) -> list[list[int]]:\n",
    "        rows = len(img)\n",
    "        cols = len(img[0])\n",
    "        tot = 0\n",
    "        res = [[0 for i in range(cols)] for i in range(rows)]\n",
    "        if rows < 3 and cols < 3:\n",
    "            for i in range(rows):\n",
    "                for j in range(cols):\n",
    "                    tot += img[i][j]\n",
    "            avr = math.floor(tot / (rows * cols))\n",
    "            for i in range(rows):\n",
    "                for j in range(cols):\n",
    "                    res[i][j] = avr\n",
    "        elif rows == 1:\n",
    "            res[0][0] = math.floor((img[0][0]+img[0][1])/2)\n",
    "            res[0][cols-1] = math.floor((img[0][cols-1] + img[0][cols-2]) / 2)\n",
    "            for i in range(1, cols-1):\n",
    "                res[0][i] = math.floor((img[0][i-1]+img[0][i]+img[0][i+1])/3)\n",
    "        elif cols == 1:\n",
    "            res[0][0] = math.floor((img[0][0] + img[1][0]) / 2)\n",
    "            res[rows-1][0] = math.floor((img[rows-1][0] + img[rows-2][0]) / 2)\n",
    "            for i in range(1, rows-1):\n",
    "                res[i][0] = math.floor((img[i-1][0]+img[i][0]+img[i+1][0])/3)\n",
    "        else:\n",
    "            for i in range(rows):\n",
    "                for j in range(cols):\n",
    "                    if i==0 and j==0:\n",
    "                        num = math.floor((img[i][j] + img[i][j + 1]+img[i + 1][j] + img[i + 1][j + 1]) / 4)\n",
    "                    elif i==0 and j==cols-1:\n",
    "                        num = math.floor((img[i][j] + img[i][j - 1] + img[i + 1][j] + img[i + 1][j - 1]) / 4)\n",
    "                    elif i == rows-1 and j == 0:\n",
    "                        num = math.floor((img[i][j] + img[i][j + 1] + img[i - 1][j] + img[i - 1][j + 1]) / 4)\n",
    "                    elif i == rows-1 and j == cols - 1:\n",
    "                        num = math.floor((img[i][j] + img[i][j - 1] + img[i - 1][j] + img[i - 1][j - 1]) / 4)\n",
    "                    elif i == 0 and 0 < j < cols-1:\n",
    "                        num = math.floor((img[i][j-1]+img[i][j]+img[i][j+1]+img[i+1][j-1]+img[i+1][j]+img[i+1][j+1])/6)\n",
    "                    elif i == rows-1 and 0 < j < cols-1:\n",
    "                        num = math.floor((img[i][j-1]+img[i][j]+img[i][j+1]+img[i-1][j-1]+img[i-1][j]+img[i-1][j+1])/6)\n",
    "                    elif 0 < i < rows-1 and j == 0:\n",
    "                        num = math.floor((img[i-1][j] + img[i-1][j+1] + img[i][j] + img[i][j + 1] + img[i + 1][j] +img[i + 1][j + 1]) / 6)\n",
    "                    elif 0 < i < rows-1 and j == cols-1:\n",
    "                        num = math.floor((img[i-1][j] + img[i-1][j-1] + img[i][j] + img[i][j - 1] + img[i + 1][j] +img[i + 1][j - 1]) / 6)\n",
    "                    else:\n",
    "                        num = math.floor((img[i - 1][j - 1] + img[i - 1][j] + img[i - 1][j + 1]\n",
    "                                          + img[i][j - 1] + img[i][j] + img[i][j + 1]\n",
    "                                          + img[i + 1][j - 1] + img[i + 1][j] + img[i + 1][j + 1]) / 9)\n",
    "                    res[i][j]=num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        if not img: return None\n",
    "        if len(img) == 1 and len(img[0]) == 1: return img\n",
    "        result = []\n",
    "        tmp=[]\n",
    "\n",
    "        if len(img) == 1:\n",
    "            for i in range(len(img[0])):\n",
    "                if i == 0: tmp.append((img[0][i] + img[0][i+1]) // 2)\n",
    "                elif i == len(img[0]) - 1: tmp.append((img[0][i] + img[0][i-1]) // 2)\n",
    "                else: tmp.append((img[0][i-1] + img[0][i] + img[0][i+1]) // 3)\n",
    "            return [tmp]\n",
    "        \n",
    "        elif len(img[0]) == 1:\n",
    "            for i in range(len(img)):\n",
    "                if i == 0: tmp = [(img[i][0] + img[i+1][0]) // 2]\n",
    "                elif i == len(img) - 1: tmp = [(img[i][0] + img[i-1][0]) // 2]\n",
    "                else: tmp = [(img[i-1][0] + img[i][0] + img[i+1][0]) // 3]\n",
    "                result.append(tmp)\n",
    "            return result\n",
    "        \n",
    "        for y in range(len(img)): \n",
    "            for x in range(len(img[y])):\n",
    "                x1, y1 = 2, 2\n",
    "                default = img[y][x]\n",
    "                if x > 0 and x < len(img[y]) - 1: x1 += 1\n",
    "                if y > 0 and y < len(img) - 1: y1 += 1\n",
    "\n",
    "                if x > 0 and x <= len(img[y]) - 1: \n",
    "                    default += img[y][x-1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x-1]  \n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x-1]  \n",
    "\n",
    "                if x >= 0 and x < len(img[y]) - 1: \n",
    "                    default += img[y][x+1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x+1]\n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x+1]\n",
    "                \n",
    "                if y > 0 and y <= len(img) - 1: default += img[y-1][x]\n",
    "                if y >= 0 and y < len(img) - 1: default += img[y+1][x]\n",
    "\n",
    "                n = x1 * y1\n",
    "                tmp.append(default // n)\n",
    "                \n",
    "            result.append(tmp)\n",
    "            tmp = []\n",
    "        return result\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\r\n",
    "        m, n = len(img), len(img[0])\r\n",
    "        ans = [[0 for _ in range(n)] for _ in range(m)]  \r\n",
    "\r\n",
    "        offsets = [[-1,-1], [0, -1], [1, -1], \r\n",
    "                   [-1, 0], [0, 0], [1, 0],\r\n",
    "                   [-1, 1], [0, 1], [1, 1]]\r\n",
    "\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                sums = 0\r\n",
    "                nums = 0\r\n",
    "                for offset in offsets:\r\n",
    "                    x, y = i + offset[0], j + offset[1]\r\n",
    "                    if (x in range(m)) and (y in range(n)):\r\n",
    "                        print(x,y)\r\n",
    "                        sums += img[x][y]\r\n",
    "                        nums += 1\r\n",
    "\r\n",
    "                ans[i][j] = math.floor(sums/nums)\r\n",
    "\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        if not img: return None\n",
    "        if len(img) == 1 and len(img[0]) == 1: return img\n",
    "        result = []\n",
    "\n",
    "        if len(img) == 1:\n",
    "            tmp=[]\n",
    "            for i in range(len(img[0])):\n",
    "                if i == 0: tmp.append((img[0][i] + img[0][i+1]) // 2)\n",
    "                elif i == len(img[0]) - 1: tmp.append((img[0][i] + img[0][i-1]) // 2)\n",
    "                else: tmp.append((img[0][i-1] + img[0][i] + img[0][i+1]) // 3)\n",
    "            return [tmp]\n",
    "        \n",
    "        if len(img[0]) == 1:\n",
    "            for i in range(len(img)):\n",
    "                if i == 0: tmp = (img[i][0] + img[i+1][0]) // 2\n",
    "                elif i == len(img) - 1: tmp = (img[i][0] + img[i-1][0]) // 2\n",
    "                else: tmp = (img[i-1][0] + img[i][0] + img[i+1][0]) // 3\n",
    "                result.append([tmp])\n",
    "            return result\n",
    "        \n",
    "        for y in range(len(img)): \n",
    "            tmp = []\n",
    "            for x in range(len(img[y])):\n",
    "                x1, y1 = 2, 2\n",
    "                default = img[y][x]\n",
    "                if x > 0 and x < len(img[y]) - 1: x1 += 1\n",
    "                if y > 0 and y < len(img) - 1: y1 += 1\n",
    "\n",
    "                if x > 0 and x <= len(img[y]) - 1: \n",
    "                    default += img[y][x-1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x-1]  \n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x-1]  \n",
    "\n",
    "                if x >= 0 and x < len(img[y]) - 1: \n",
    "                    default += img[y][x+1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x+1]\n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x+1]\n",
    "                \n",
    "                if y > 0 and y <= len(img) - 1: default += img[y-1][x]\n",
    "                if y >= 0 and y < len(img) - 1: default += img[y+1][x]\n",
    "\n",
    "                n = x1 * y1\n",
    "                tmp.append(default // n)\n",
    "            result.append(tmp)\n",
    "        return result\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        if not img: return None\n",
    "        if len(img) == 1 and len(img[0]) == 1: return img\n",
    "        result = []\n",
    "        tmp=[]\n",
    "\n",
    "        if len(img) == 1:\n",
    "            for i in range(len(img[0])):\n",
    "                if i == 0: tmp.append((img[0][i] + img[0][i+1]) // 2)\n",
    "                elif i == len(img[0]) - 1: tmp.append((img[0][i] + img[0][i-1]) // 2)\n",
    "                else: tmp.append((img[0][i-1] + img[0][i] + img[0][i+1]) // 3)\n",
    "            return [tmp]\n",
    "        \n",
    "        if len(img[0]) == 1:\n",
    "            for i in range(len(img)):\n",
    "                if i == 0: tmp = (img[i][0] + img[i+1][0]) // 2\n",
    "                elif i == len(img) - 1: tmp = (img[i][0] + img[i-1][0]) // 2\n",
    "                else: tmp = (img[i-1][0] + img[i][0] + img[i+1][0]) // 3\n",
    "                result.append([tmp])\n",
    "            return result\n",
    "        \n",
    "        for y in range(len(img)): \n",
    "            tmp = []\n",
    "            for x in range(len(img[y])):\n",
    "                x1, y1 = 2, 2\n",
    "                default = img[y][x]\n",
    "                if x > 0 and x < len(img[y]) - 1: x1 += 1\n",
    "                if y > 0 and y < len(img) - 1: y1 += 1\n",
    "\n",
    "                if x > 0 and x <= len(img[y]) - 1: \n",
    "                    default += img[y][x-1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x-1]  \n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x-1]  \n",
    "\n",
    "                if x >= 0 and x < len(img[y]) - 1: \n",
    "                    default += img[y][x+1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x+1]\n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x+1]\n",
    "                \n",
    "                if y > 0 and y <= len(img) - 1: default += img[y-1][x]\n",
    "                if y >= 0 and y < len(img) - 1: default += img[y+1][x]\n",
    "\n",
    "                n = x1 * y1\n",
    "                tmp.append(default // n)\n",
    "            result.append(tmp)\n",
    "        return result\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(img)\n",
    "        n = len(img[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,y,tmp=0):\n",
    "            total = 9\n",
    "            count = img[x][y]\n",
    "            for i,j in [[x+1,y],[x-1,y],[x,y+1],[x,y-1],[x+1,y-1],[x+1,y+1],[x-1,y-1],[x-1,y+1]]:\n",
    "                if not(0<=i<m and 0<=j<n):\n",
    "                    total -= 1\n",
    "                else:\n",
    "                    count += img[i][j]\n",
    "            return count//total\n",
    "        res = [[0 for y in range(n)] for x in range(m)]\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                res[x][y] = dfs(x,y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        if not img: return None\n",
    "        if len(img) == 1 and len(img[0]) == 1: return img\n",
    "        result = []\n",
    "\n",
    "        if len(img) == 1:\n",
    "            tmp=[]\n",
    "            for i in range(len(img[0])):\n",
    "                if i == 0: tmp.append(int((img[0][i] + img[0][i+1]) / 2))\n",
    "                elif i == len(img[0]) - 1: tmp.append(int((img[0][i] + img[0][i-1]) / 2))\n",
    "                else: tmp.append(int((img[0][i-1] + img[0][i] + img[0][i+1]) / 3))\n",
    "            return [tmp]\n",
    "        \n",
    "        if len(img[0]) == 1:\n",
    "            for i in range(len(img)):\n",
    "                if i == 0: tmp = [int((img[i][0] + img[i+1][0]) / 2)]\n",
    "                elif i == len(img) - 1: tmp = [int((img[i][0] + img[i-1][0]) / 2)]\n",
    "                else: tmp = [int((img[i-1][0] + img[i][0] + img[i+1][0]) / 3)]\n",
    "                result.append(tmp)\n",
    "            return result\n",
    "        \n",
    "        for y in range(len(img)): \n",
    "            tmp = []\n",
    "            for x in range(len(img[y])):\n",
    "                x1, y1 = 2, 2\n",
    "                default = img[y][x]\n",
    "                if x > 0 and x < len(img[y]) - 1: x1 += 1\n",
    "                if y > 0 and y < len(img) - 1: y1 += 1\n",
    "\n",
    "                if x > 0 and x <= len(img[y]) - 1: \n",
    "                    default += img[y][x-1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x-1]  \n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x-1]  \n",
    "\n",
    "                if x >= 0 and x < len(img[y]) - 1: \n",
    "                    default += img[y][x+1]\n",
    "                    if y > 0 and y <= len(img) - 1: default += img[y-1][x+1]\n",
    "                    if y >= 0 and y < len(img) - 1: default += img[y+1][x+1]\n",
    "                \n",
    "                if y > 0 and y <= len(img) - 1: default += img[y-1][x]\n",
    "                if y >= 0 and y < len(img) - 1: default += img[y+1][x]\n",
    "\n",
    "                n = x1 * y1\n",
    "                tmp.append(int(str(default / n)[:str(default / n).find(\".\")]))\n",
    "            result.append(tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        preList = list([0 for y in range(len(img[0]))] for x in range(len(img)))\n",
    "        resList = list([0 for y in range(len(img[0]))] for x in range(len(img)))\n",
    "        for y in range(len(img)):\n",
    "            preSum = 0\n",
    "            for x in range(len(img[0])):\n",
    "                preSum += img[y][x]\n",
    "                preList[y][x] = preSum\n",
    "                if y > 0:\n",
    "                    preList[y][x] += preList[y-1][x]\n",
    "        def getValue(preList, y, x):\n",
    "            h, w = len(preList), len(preList[0])\n",
    "            y1, x1 = y-2, x-2\n",
    "            y2, x2 = min(y+1, h-1), min(x+1, w-1)\n",
    "            val = preList[y2][x2]\n",
    "            if y1 >= 0:\n",
    "                val -= preList[y1][x2]\n",
    "            if x1 >= 0:\n",
    "                val -= preList[y2][x1]\n",
    "            if y1 >= 0 and x1 >= 0:\n",
    "                val += preList[y1][x1]\n",
    "            num = (y2 - max(y1, -1)) * (x2 - max(x1, -1))\n",
    "            return val // num\n",
    "        for y in range(len(img)):\n",
    "            for x in range(len(img[0])):\n",
    "                resList[y][x] = getValue(preList, y, x)\n",
    "        return resList\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "#         dp = [[0]*i for i in range(len(img))]\n",
    "#         dp[0][0] = ()\n",
    "#         a1 = [0, -1]\n",
    "#         for a in a1:\n",
    "#             dp[a][a] = sum(img[a][a])//4\n",
    "#         for b in range(1, -1):\n",
    "#             dp[b][0] = sum(dp[b][0]+dp[b][1]+dp[b+1][0]+dp[b+1][1]+dp[b+2][0]+dp[b+2][1])//6\n",
    "#             dp[b][-1] = sum(dp[b][0]+dp[b][1]+dp[b+1][0]+dp[b+1][1]+dp[b+2][0]+dp[b+2][1])//6\n",
    "#             dp[b][0] = sum(dp[b][0]+dp[b][1]+dp[b+1][0]+dp[b+1][1]+dp[b+2][0]+dp[b+2][1])//6\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        sum = [[0] * (n + 10) for _ in range(m + 10)]\n",
    "        for i, j in product(range(1, m + 1), range(1, n + 1)):\n",
    "            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            a, b = max(0, i - 1), max(0, j - 1)\n",
    "            c, d = min(m - 1, i + 1), min(n - 1, j + 1)\n",
    "            cnt = (c - a + 1) * (d - b + 1)\n",
    "            tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        if img == [[1]]:\n",
    "            return([[1]])\n",
    "        t = []\n",
    "        t1=[]\n",
    "        if len(img) == 1:\n",
    "            t1.append(int((img[0][0] + img[0][1]) // 2))\n",
    "            t1.append(int((img[0][-1] + img[0][-2]) // 2))\n",
    "            for x in range(len(img[0]) - 2):\n",
    "                t1.insert(-1, int((img[0][x] + img[0][x + 1] + img[0][x + 2]) // 3))\n",
    "            t.append(t1)\n",
    "            return(t)\n",
    "        if len(img[0]) == 1:\n",
    "            t.append([int((img[0][0] + img[1][0]) // 2)])\n",
    "            t.append([int((img[-1][0] + img[-2][0]) // 2)])\n",
    "            for x in range(len(img) - 2):\n",
    "                t.insert(-1, [int((img[x + 1][0] + img[x + 2][0]+img[x][0]) // 3)])\n",
    "            return t\n",
    "        xl = len(img[0])\n",
    "        yl = len(img)\n",
    "        for x in range(len(img)):\n",
    "            img[x].insert(0, 0)\n",
    "            img[x].append(0)\n",
    "        img.insert(0, [0] * (xl + 2))\n",
    "        img.append([0] * (xl + 2))\n",
    "        s = 0\n",
    "        t = []\n",
    "        for y in range(yl):\n",
    "            t1 = []\n",
    "            for x in range(xl):\n",
    "                s += img[y][0 + x] + img[y][1 + x] + img[y][2 + x] + \\\n",
    "                    img[y + 1][0 + x] + img[y + 1][1 + x] + img[y + 1][2 + x] \\\n",
    "                    + img[y + 2][0 + x] + img[y + 2][1 + x] + img[y + 2][2 + x]\n",
    "                if y == 0 and x == 0 or y == 0 and x == xl - 1 or y == yl - 1 and x == 0 or y == yl - 1 and x == xl - 1:\n",
    "\n",
    "                    s = int((s / 4) // 1)\n",
    "\n",
    "                elif x == 0 or x == xl - 1 or y == 0 or y == yl - 1:\n",
    "\n",
    "                    s = int((s / 6) // 1)\n",
    "\n",
    "                else:\n",
    "                    s = int((s / 9) // 1)\n",
    "\n",
    "                t1.append(s)\n",
    "                s = 0\n",
    "            t.append(t1)\n",
    "\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(img), len(img[0])\n",
    "        pref = [[0 for _ in range(m+4)] for _ in range(n+4)]\n",
    "        nimg = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        for x in range(n + 2):\n",
    "            for y in range(m + 2):\n",
    "                pref[x+2][y+2] = pref[x+1][y+2] + pref[x+2][y+1] - pref[x+1][y+1]\n",
    "                if x < n and y < m:\n",
    "                    pref[x+2][y+2] += img[x][y]\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                nimg[x][y] = (pref[x+3][y+3] - pref[x+3][y] - pref[x][y+3] + pref[x][y]) // ((min(n, x+2) - max(0, x-1)) * (min(m, y+2) - max(0, y-1)))\n",
    "        return nimg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(img)\n",
    "        n = len(img[0])\n",
    "        mats = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat = [img[i][j]]\n",
    "                if i-1>=0:\n",
    "                    mat.append(img[i-1][j])\n",
    "                    if j-1>=0:\n",
    "                        mat.append(img[i-1][j-1])\n",
    "                    if j+1<n:\n",
    "                        mat.append(img[i-1][j+1])\n",
    "                if i+1<m:\n",
    "                    mat.append(img[i+1][j])\n",
    "                    if j-1>=0:\n",
    "                        mat.append(img[i+1][j-1])\n",
    "                    if j+1<n:\n",
    "                        mat.append(img[i+1][j+1])\n",
    "                if j-1>=0:\n",
    "                    mat.append(img[i][j-1])\n",
    "                if j+1<n:\n",
    "                    mat.append(img[i][j+1])\n",
    "\n",
    "                mats.append(math.floor(sum(mat)/len(mat)))\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            res.append(mats[i*n:(i+1)*n])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[] for _ in range(len(img))]\n",
    "        e = []\n",
    "        for i in range(len(img)):\n",
    "            for j in range(len(img[0])):\n",
    "                t = 0\n",
    "                c = 0\n",
    "                for n in range(max(0,i-1),min(i+2,len(img))):\n",
    "                    \n",
    "                    for m in range(max(0,j-1),min(j+2,len(img[0]))):\n",
    "                        t+= img[n][m]\n",
    "                        c+=1\n",
    "                e.append([t,c])\n",
    "                t/=c\n",
    "               \n",
    "                res[i].append(int(t))\n",
    "        print(e)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        # 初始化累积和矩阵\n",
    "        prefix_sum = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prefix_sum[i+1][j+1] = img[i][j] + prefix_sum[i][j+1] + prefix_sum[i+1][j] - prefix_sum[i][j]\n",
    "        \n",
    "        def get_sum(x1, y1, x2, y2):\n",
    "            return prefix_sum[x2][y2] - prefix_sum[x2][y1] - prefix_sum[x1][y2] + prefix_sum[x1][y1]\n",
    "        \n",
    "        smoothed_img = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x1, y1, x2, y2 = max(0, i-1), max(0, j-1), min(m, i+2), min(n, j+2)\n",
    "                total_value = get_sum(x1, y1, x2, y2)\n",
    "                count = (x2 - x1) * (y2 - y1)  # 相乘是因为我们得到的是矩阵的尺寸\n",
    "                smoothed_img[i][j] = total_value // count\n",
    "                \n",
    "        return smoothed_img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        sum = [[0] * (n + 10) for _ in range(m + 10)]\n",
    "        for i, j in product(range(1, m + 1), range(1, n + 1)):\n",
    "            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            a, b = max(0, i - 1), max(0, j - 1)\n",
    "            c, d = min(m - 1, i + 1), min(n - 1, j + 1)\n",
    "            cnt = (c - a + 1) * (d - b + 1)\n",
    "            tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(img)\n",
    "        n = len(img[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,y,tmp=0):\n",
    "            total = 9\n",
    "            count = img[x][y]\n",
    "            for i,j in [[x+1,y],[x-1,y],[x,y+1],[x,y-1],[x+1,y-1],[x+1,y+1],[x-1,y-1],[x-1,y+1]]:\n",
    "                if not(0<=i<m and 0<=j<n):\n",
    "                    total -= 1\n",
    "                else:\n",
    "                    count += img[i][j]\n",
    "            return count//total\n",
    "        res = [[0 for y in range(n)] for x in range(m)]\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                res[x][y] = dfs(x,y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\r\n",
    "        m, n = len(img), len(img[0])\r\n",
    "        sum = [[0] * (n + 10) for _ in range(m + 10)]\r\n",
    "        for i, j in product(range(1, m + 1), range(1, n + 1)):\r\n",
    "            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]\r\n",
    "        ans = [[0] * n for _ in range(m)]\r\n",
    "        for i, j in product(range(m), range(n)):\r\n",
    "            a, b = max(0, i - 1), max(0, j - 1)\r\n",
    "            c, d = min(m - 1, i + 1), min(n - 1, j + 1)\r\n",
    "            cnt = (c - a + 1) * (d - b + 1)\r\n",
    "            tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]\r\n",
    "            ans[i][j] = tot // cnt\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        sum = [[0] * (n + 10) for _ in range(m + 10)]\n",
    "        for i, j in product(range(1, m + 1), range(1, n + 1)):\n",
    "            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            a, b = max(0, i - 1), max(0, j - 1)\n",
    "            c, d = min(m - 1, i + 1), min(n - 1, j + 1)\n",
    "            cnt = (c - a + 1) * (d - b + 1)\n",
    "            tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        sum = [[0] * (n + 10) for _ in range(m + 10)]\n",
    "        for i, j in product(range(1, m + 1), range(1, n + 1)):\n",
    "            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            a, b = max(0, i - 1), max(0, j - 1)\n",
    "            c, d = min(m - 1, i + 1), min(n - 1, j + 1)\n",
    "            cnt = (c - a + 1) * (d - b + 1)\n",
    "            tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        # 初始化累积和矩阵\n",
    "        prefix_sum = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prefix_sum[i+1][j+1] = img[i][j] + prefix_sum[i][j+1] + prefix_sum[i+1][j] - prefix_sum[i][j]\n",
    "        \n",
    "        def get_sum(x1, y1, x2, y2):\n",
    "            return prefix_sum[x2][y2] - prefix_sum[x2][y1] - prefix_sum[x1][y2] + prefix_sum[x1][y1]\n",
    "        \n",
    "        smoothed_img = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x1, y1, x2, y2 = max(0, i-1), max(0, j-1), min(m, i+2), min(n, j+2)\n",
    "                total_value = get_sum(x1, y1, x2, y2)\n",
    "                count = (x2 - x1) * (y2 - y1)  # 相乘是因为我们得到的是矩阵的尺寸\n",
    "                smoothed_img[i][j] = total_value // count\n",
    "                \n",
    "        return smoothed_img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        presum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i + 1][j + 1] = presum[i + 1][j] + presum[i][j + 1] - presum[i][j] + img[i][j]\n",
    "        return [[(presum[(mxi := min(m, i + 2))][(mxj := min(n, j + 2))] - presum[(mii := max(0, i - 1))][mxj] - presum[mxi][(mij := max(0, j - 1))] + presum[mii][mij]) // ((mxi - mii) * (mxj - mij)) for j in range(n)] for i in range(m)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        sum = [[0] * (n + 10) for _ in range(m + 10)]\n",
    "        for i, j in product(range(1, m + 1), range(1, n + 1)):\n",
    "            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            a, b = max(0, i - 1), max(0, j - 1)\n",
    "            c, d = min(m - 1, i + 1), min(n - 1, j + 1)\n",
    "            cnt = (c - a + 1) * (d - b + 1)\n",
    "            total = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]\n",
    "            ans[i][j] = total // cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(img), len(img[0])\n",
    "        sum = [[0] * (n + 10) for _ in range(m + 10)]\n",
    "        for i, j in product(range(1, m + 1), range(1, n + 1)):\n",
    "            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            a, b = max(0, i - 1), max(0, j - 1)\n",
    "            c, d = min(m - 1, i + 1), min(n - 1, j + 1)\n",
    "            cnt = (c - a + 1) * (d - b + 1)\n",
    "            tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]\n",
    "            ans[i][j] = tot // cnt\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
